/*
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。
所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1. 算法步骤
    a.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
    b.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
    c.重复第二步，直到所有元素均排序完毕。
 */

/**
 * 遍历数组，将当前元素与右侧元素逐个进行比较，选出右侧最小的元素下标后，与当前元素调换位置
 * @param arr
 * @return {*}
 */
function selectSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        let index = i
        for (let j = i + 1; j < arr.length; j++) {
            // 降序排序 arr[index] < arr[j]
            // 升序排序 arr[index] > arr[j]
            if (arr[index] > arr[j]) {
                index = j
            }
        }
        // 找到了比arr[i]小的则与arr[i]交换位置
        if (index !== i) {
            let temp = arr[i]
            arr[i] = arr[index]
            arr[index] = temp
        }
    }
    return arr
}

console.log(selectSort([9, 1, 5, 4, 12, 33, 0]))
console.log(selectSort([9, 1, 5, 4, 12, 33, 0, 5]))
console.log(selectSort([9, 1, 5, 4, 12, 33, 0, 12.2, 2.5, 5.3, 4]))

// [ 0, 1, 4, 5, 9, 12, 33 ]
// [ 0, 1, 4, 5, 5, 9, 12, 33 ]
// [ 0, 1, 2.5, 4, 4, 5, 5.3, 9, 12, 12.2, 33 ]
